package a00_LeetCode.LinkedList;

import javax.xml.soap.Node;

/**
 * @Author quan
 * @Description 移除链表元素
 * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
 * @Date 2023/3/20 18:58
 */
public class Num203_removeElement {
   /* public ListNode removeElements(ListNode head, int val) {
        *//**
         * 方法1：虚拟头结点法：只使用一个指针
         * 思路：遍历链表，走到被删除节点的前驱，与要删除的值比较，更改指向
         *//*
        //判断边界条件:链表中不存在节点，则直接返回Null
        if(head == null){
            return null;
        }
        //产生一个虚拟头结点
        ListNode dummyNode = new ListNode();
        //将虚拟头结点与原链表建立联系
        dummyNode.next = head;
        //让prev作为临时节点代替head
        ListNode prev = dummyNode;
        while (prev.next != null){
            if(prev.next.val == val){
                prev.next = prev.next.next;
            }else{
                prev = prev.next;//防止出现连续的被删除的节点，只有当prev.next不是被删除的节点时才移动
            }
        }
        return dummyNode.next;
    }*/
    /**
     * 虚拟头结点法：使用两个指针
     */
   /* public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == val){
                prev.next = cur.next;
            }else{
                prev = cur;
            }
            cur = cur.next;
        }
        return dummyHead.next;
    }*/
    /**
     * 方法2：在原链表上删除:双指针法
     */
    /*public ListNode removeElements(ListNode head, int val) {
        //处理头结点
        while (head!=null && head.val==val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        //此时头节点一定不是被删除的节点
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur!=null){
            if(cur.val == val){
                prev.next = cur.next;
            }else{
                prev = cur;
            }
            cur = cur.next;
        }
        return head;
    }*/
    /**
     * 在原链表上删除：单指针法
     */
    public ListNode removeElements(ListNode head, int val) {
        //处理头结点
        while (head!=null && head.val==val){
            head = head.next;
        }
        if(head == null){
            return null;
        }
        ListNode prev= head;
        while (prev!=null){
            while (prev.next!=null && prev.next.val == val){
                prev.next = prev.next.next;
            }
            prev = prev.next;
        }
        return head;
    }
        /**
         * 方法2：递归法
         */
    /*public ListNode removeElements(ListNode head, int val) {

        //边界条件
        if(head == null){
            return null;
        }
        //正常情况
        //先把以head.next为头结点的子链表中的所有为val中的值删除完毕！
        head.next = removeElements(head.next,val);
        //最后判断头结点的情况：是否需要删除
        return head.val == val ? head.next:head;
    }*/
}
